
//最长回文子串:https://leetcode.cn/problems/longest-palindromic-substring/?envType=study-plan-v2&envId=top-100-liked
//方法1:中心拓展法；
//方法2:先列举出所有的子串，然后再逐个判断是否回文；
//方法3:manacher算法；

#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) 
    {
        if (s.length() < 1)
        {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++)
        {
            int len1 = expandAroundCenter(s, i, i);//一个元素为中心
            int len2 = expandAroundCenter(s, i, i + 1);//两个元素为中心
            int len = max(len1, len2);
            if (len > end - start)
            {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substr(start, end - start + 1);
    }

    int expandAroundCenter(string s, int left, int right)
    {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s[L] == s[R])
        {// 计算以left和right为中心的回文串长度
            L--;
            R++;
        }
        return R - L - 1;
    }
};



class Solution2 {
public:
    string longestPalindrome(string s) {
    
        string max_str;
        std::vector<std::string> substrings;
        for (size_t i = 0; i < s.length(); ++i) {
            for (size_t j = i + 1; j <= s.length(); ++j) {
                std::string sub_str=s.substr(i, j - i);
                if(isPalindrome(sub_str)){
                    if(sub_str.size()>max_str.size()){
                        max_str=sub_str;
                    }
                }
            }
        }
        return max_str;
    }
    bool isPalindrome(std::string str){
        int left=0;
        int right=str.size()-1;
        while(left<right){
            if(str[left]!=str[right]){
                return false;
            }
            ++left;
            --right;
        }
        return true;

    }
};